Search Results

Documents authored by Censor-Hillel, Keren

Document
DOI: 10.4230/LIPIcs.ITCS.2022.35
Quantum Distributed Algorithms for Detection of Cliques

Authors: Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
The possibilities offered by quantum computing have drawn attention in the distributed computing community recently, with several breakthrough results showing quantum distributed algorithms that run faster than the fastest known classical counterparts, and even separations between the two models. A prime example is the result by Izumi, Le Gall, and Magniez [STACS 2020], who showed that triangle detection by quantum distributed algorithms is easier than triangle listing, while an analogous result is not known in the classical case. In this paper we present a framework for fast quantum distributed clique detection. This improves upon the state-of-the-art for the triangle case, and is also more general, applying to larger clique sizes. Our main technical contribution is a new approach for detecting cliques by encapsulating this as a search task for nodes that can be added to smaller cliques. To extract the best complexities out of our approach, we develop a framework for nested distributed quantum searches, which employ checking procedures that are quantum themselves. Moreover, we show a circuit-complexity barrier on proving a lower bound of the form Ω(n^{3/5+ε}) for K_p-detection for any p ≥ 4, even in the classical (non-quantum) distributed CONGEST setting.
Cite as

Keren Censor-Hillel, Orr Fischer, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Quantum Distributed Algorithms for Detection of Cliques. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 35:1-35:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2022.35,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Quantum Distributed Algorithms for Detection of Cliques}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{35:1--35:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.35},
  URN =		{urn:nbn:de:0030-drops-156319},
  doi =		{10.4230/LIPIcs.ITCS.2022.35},
  annote =	{Keywords: distributed graph algorithms, quantum algorithms, cycles, cliques, Congested Clique, CONGEST}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2022.36
Distributed Vertex Cover Reconfiguration

Authors: Keren Censor-Hillel, Yannic Maus, Shahar Romem-Peled, and Tigran Tonoyan

Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)

Abstract
Reconfiguration schedules, i.e., sequences that gradually transform one solution of a problem to another while always maintaining feasibility, have been extensively studied. Most research has dealt with the decision problem of whether a reconfiguration schedule exists, and the complexity of finding one. A prime example is the reconfiguration of vertex covers. We initiate the study of batched vertex cover reconfiguration, which allows to reconfigure multiple vertices concurrently while requiring that any adversarial reconfiguration order within a batch maintains feasibility. The latter provides robustness, e.g., if the simultaneous reconfiguration of a batch cannot be guaranteed. The quality of a schedule is measured by the number of batches until all nodes are reconfigured, and its cost, i.e., the maximum size of an intermediate vertex cover. To set a baseline for batch reconfiguration, we show that for graphs belonging to one of the classes {{cycles, trees, forests, chordal, cactus, even-hole-free, claw-free}}, there are schedules that use O(ε^{-1}) batches and incur only a 1+ε multiplicative increase in cost over the best sequential schedules. Our main contribution is to compute such batch schedules in a distributed setting O(ε^{-1} {log^*} n) rounds, which we also show to be tight. Further, we show that once we step out of these graph classes we face a very different situation. There are graph classes on which no efficient distributed algorithm can obtain the best (or almost best) existing schedule. Moreover, there are classes of bounded degree graphs which do not admit any reconfiguration schedules without incurring a large multiplicative increase in the cost at all.
Cite as

Keren Censor-Hillel, Yannic Maus, Shahar Romem-Peled, and Tigran Tonoyan. Distributed Vertex Cover Reconfiguration. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 36:1-36:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2022.36,
  author =	{Censor-Hillel, Keren and Maus, Yannic and Romem-Peled, Shahar and Tonoyan, Tigran},
  title =	{{Distributed Vertex Cover Reconfiguration}},
  booktitle =	{13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
  pages =	{36:1--36:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-217-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{215},
  editor =	{Braverman, Mark},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.36},
  URN =		{urn:nbn:de:0030-drops-156327},
  doi =		{10.4230/LIPIcs.ITCS.2022.36},
  annote =	{Keywords: reconfiguration, vertex cover, network decomposition}
}
Document
DOI: 10.4230/LIPIcs.DISC.2021.8
Locally Checkable Labelings with Small Messages

Authors: Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela

Published in: LIPIcs, Volume 209, 35th International Symposium on Distributed Computing (DISC 2021)

Abstract
A rich line of work has been addressing the computational complexity of locally checkable labelings (LCLs), illustrating the landscape of possible complexities. In this paper, we study the landscape of LCL complexities under bandwidth restrictions. Our main results are twofold. First, we show that on trees, the CONGEST complexity of an LCL problem is asymptotically equal to its complexity in the LOCAL model. An analog statement for non-LCL problems is known to be false. Second, we show that for general graphs this equivalence does not hold, by providing an LCL problem for which we show that it can be solved in O(log n) rounds in the LOCAL model, but requires Ω̃(n^{1/2}) rounds in the CONGEST model.
Cite as

Alkida Balliu, Keren Censor-Hillel, Yannic Maus, Dennis Olivetti, and Jukka Suomela. Locally Checkable Labelings with Small Messages. In 35th International Symposium on Distributed Computing (DISC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 209, pp. 8:1-8:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{balliu_et_al:LIPIcs.DISC.2021.8,
  author =	{Balliu, Alkida and Censor-Hillel, Keren and Maus, Yannic and Olivetti, Dennis and Suomela, Jukka},
  title =	{{Locally Checkable Labelings with Small Messages}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{8:1--8:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2021.8},
  URN =		{urn:nbn:de:0030-drops-148109},
  doi =		{10.4230/LIPIcs.DISC.2021.8},
  annote =	{Keywords: distributed graph algorithms, CONGEST, locally checkable labelings}
}
Document
Invited Talk
DOI: 10.4230/LIPIcs.ICALP.2021.3
Distributed Subgraph Finding: Progress and Challenges (Invited Talk)

Authors: Keren Censor-Hillel

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
This is a survey of the exciting recent progress made in understanding the complexity of distributed subgraph finding problems. It overviews the results and techniques for assorted variants of subgraph finding problems in various models of distributed computing, and states intriguing open questions.
Cite as

Keren Censor-Hillel. Distributed Subgraph Finding: Progress and Challenges (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 3:1-3:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel:LIPIcs.ICALP.2021.3,
  author =	{Censor-Hillel, Keren},
  title =	{{Distributed Subgraph Finding: Progress and Challenges}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{3:1--3:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.3},
  URN =		{urn:nbn:de:0030-drops-140726},
  doi =		{10.4230/LIPIcs.ICALP.2021.3},
  annote =	{Keywords: distributed algorithms, subgraph finding, limited bandwidth}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.46
Fault Tolerant Max-Cut

Authors: Keren Censor-Hillel, Noa Marelly, Roy Schwartz, and Tigran Tonoyan

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
In this work, we initiate the study of fault tolerant Max-Cut, where given an edge-weighted undirected graph G = (V,E), the goal is to find a cut S ⊆ V that maximizes the total weight of edges that cross S even after an adversary removes k vertices from G. We consider two types of adversaries: an adaptive adversary that sees the outcome of the random coin tosses used by the algorithm, and an oblivious adversary that does not. For any constant number of failures k we present an approximation of (0.878-ε) against an adaptive adversary and of α_{GW}≈ 0.8786 against an oblivious adversary (here α_{GW} is the approximation achieved by the random hyperplane algorithm of [Goemans-Williamson J. ACM `95]). Additionally, we present a hardness of approximation of α_{GW} against both types of adversaries, rendering our results (virtually) tight. The non-linear nature of the fault tolerant objective makes the design and analysis of algorithms harder when compared to the classic Max-Cut. Hence, we employ approaches ranging from multi-objective optimization to LP duality and the ellipsoid algorithm to obtain our results.
Cite as

Keren Censor-Hillel, Noa Marelly, Roy Schwartz, and Tigran Tonoyan. Fault Tolerant Max-Cut. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 46:1-46:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2021.46,
  author =	{Censor-Hillel, Keren and Marelly, Noa and Schwartz, Roy and Tonoyan, Tigran},
  title =	{{Fault Tolerant Max-Cut}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{46:1--46:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.46},
  URN =		{urn:nbn:de:0030-drops-141158},
  doi =		{10.4230/LIPIcs.ICALP.2021.46},
  annote =	{Keywords: fault-tolerance, max-cut, approximation}
}
Document
DOI: 10.4230/LIPIcs.STACS.2021.21
Distance Computations in the Hybrid Network Model via Oracle Simulations

Authors: Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin

Published in: LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Abstract
The Hybrid network model was introduced in [Augustine et al., SODA '20] for laying down a theoretical foundation for networks which combine two possible modes of communication: One mode allows high-bandwidth communication with neighboring nodes, and the other allows low-bandwidth communication over few long-range connections at a time. This fundamentally abstracts networks such as hybrid data centers, and class-based software-defined networks. Our technical contribution is a density-aware approach that allows us to simulate a set of oracles for an overlay skeleton graph over a Hybrid network. As applications of our oracle simulations, with additional machinery that we provide, we derive fast algorithms for fundamental distance-related tasks. One of our core contributions is an algorithm in the Hybrid model for computing exact weighted shortest paths from Õ(n^{1/3}) sources which completes in Õ(n^{1/3}) rounds w.h.p. This improves, in both the runtime and the number of sources, upon the algorithm of [Kuhn and Schneider, PODC ’20], which computes shortest paths from a single source in Õ(n^{2/5}) rounds w.h.p. We additionally show a 2-approximation for weighted diameter and a (1+ε)-approximation for unweighted diameter, both in Õ(n^{1/3}) rounds w.h.p., which is comparable to the ̃ Ω(n^{1/3}) lower bound of [Kuhn and Schneider, PODC ’20] for a (2-ε)-approximation for weighted diameter and an exact unweighted diameter. We also provide fast distance approximations from multiple sources and fast approximations for eccentricities.
Cite as

Keren Censor-Hillel, Dean Leitersdorf, and Volodymyr Polosukhin. Distance Computations in the Hybrid Network Model via Oracle Simulations. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 21:1-21:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.STACS.2021.21,
  author =	{Censor-Hillel, Keren and Leitersdorf, Dean and Polosukhin, Volodymyr},
  title =	{{Distance Computations in the Hybrid Network Model via Oracle Simulations}},
  booktitle =	{38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
  pages =	{21:1--21:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-180-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{187},
  editor =	{Bl\"{a}ser, Markus and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.21},
  URN =		{urn:nbn:de:0030-drops-136663},
  doi =		{10.4230/LIPIcs.STACS.2021.21},
  annote =	{Keywords: Distributed graph algorithms, Hybrid network model, Distance computations}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.28
Fast Deterministic Algorithms for Highly-Dynamic Networks

Authors: Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
This paper provides an algorithmic framework for obtaining fast distributed algorithms for a highly-dynamic setting, in which arbitrarily many edge changes may occur in each round. Our algorithm significantly improves upon prior work in its combination of (1) having an O(1) amortized time complexity, (2) using only O(log{n})-bit messages, (3) not posing any restrictions on the dynamic behavior of the environment, (4) being deterministic, (5) having strong guarantees for intermediate solutions, and (6) being applicable for a wide family of tasks. The tasks for which we deduce such an algorithm are maximal matching, (degree+1)-coloring, 2-approximation for minimum weight vertex cover, and maximal independent set (which is the most subtle case). For some of these tasks, node insertions can also be among the allowed topology changes, and for some of them also abrupt node deletions.
Cite as

Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman. Fast Deterministic Algorithms for Highly-Dynamic Networks. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2020.28,
  author =	{Censor-Hillel, Keren and Dafni, Neta and Kolobov, Victor I. and Paz, Ami and Schwartzman, Gregory},
  title =	{{Fast Deterministic Algorithms for Highly-Dynamic Networks}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.28},
  URN =		{urn:nbn:de:0030-drops-135138},
  doi =		{10.4230/LIPIcs.OPODIS.2020.28},
  annote =	{Keywords: dynamic distributed algorithms}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2020.30
Distributed Distance Approximation

Authors: Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, and Virginia Vassilevska Williams

Published in: LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020)

Abstract
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can be much more efficient compared with computing exact solutions. In this paper, we give a near complete characterization of the trade-offs between approximation ratios and round complexity of distributed algorithms for approximating these parameters, with a focus on the weighted and directed variants. Furthermore, we study bi-chromatic variants of these parameters defined on a graph whose vertices are colored either red or blue, and one focuses only on distances for pairs of vertices that are colored differently. Motivated by applications in computational geometry, bi-chromatic diameter, radius and eccentricities have been recently studied in the sequential setting [Backurs et al. STOC'18, Dalirrooyfard et al. ICALP'19]. We provide the first distributed upper and lower bounds for such problems. Our technical contributions include introducing the notion of approximate pseudo-center, which extends the pseudo-centers of [Choudhary and Gold SODA'20], and presenting an efficient distributed algorithm for computing approximate pseudo-centers. On the lower bound side, our constructions introduce the usage of new functions into the framework of reductions from 2-party communication complexity to distributed algorithms.
Cite as

Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard, Yuval Efron, and Virginia Vassilevska Williams. Distributed Distance Approximation. In 24th International Conference on Principles of Distributed Systems (OPODIS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 184, pp. 30:1-30:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{ancona_et_al:LIPIcs.OPODIS.2020.30,
  author =	{Ancona, Bertie and Censor-Hillel, Keren and Dalirrooyfard, Mina and Efron, Yuval and Vassilevska Williams, Virginia},
  title =	{{Distributed Distance Approximation}},
  booktitle =	{24th International Conference on Principles of Distributed Systems (OPODIS 2020)},
  pages =	{30:1--30:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-176-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{184},
  editor =	{Bramas, Quentin and Oshman, Rotem and Romano, Paolo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.30},
  URN =		{urn:nbn:de:0030-drops-135150},
  doi =		{10.4230/LIPIcs.OPODIS.2020.30},
  annote =	{Keywords: Distributed Computing, Distance Computation, Algorithms, Lower Bounds}
}
Document
DOI: 10.4230/LIPIcs.DISC.2020.33
Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs

Authors: Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman

Published in: LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020)

Abstract
In this paper we give fast distributed graph algorithms for detecting and listing small subgraphs, and for computing or approximating the girth. Our algorithms improve upon the state of the art by polynomial factors, and for girth, we obtain a constant-time algorithm for additive +1 approximation in Congested Clique, and the first parametrized algorithm for exact computation in Congest. In the Congested Clique model, we first develop a technique for learning small neighborhoods, and apply it to obtain an O(1)-round algorithm that computes the girth with only an additive +1 error. Next, we introduce a new technique (the partition tree technique) allowing for efficiently listing all copies of any subgraph, which is deterministic and improves upon the state-of the-art for non-dense graphs. We give two concrete applications of the partition tree technique: First we show that for constant k, it is possible to solve C_{2k}-detection in O(1) rounds in the Congested Clique, improving on prior work, which used fast matrix multiplication and thus had polynomial round complexity. Second, we show that in triangle-free graphs, the girth can be exactly computed in time polynomially faster than the best known bounds for general graphs. We remark that no analogous result is currently known for sequential algorithms. In the Congest model, we describe a new approach for finding cycles, and instantiate it in two ways: first, we show a fast parametrized algorithm for girth with round complexity Õ(min{g⋅ n^{1-1/Θ(g)},n}) for any girth g; and second, we show how to find small even-length cycles C_{2k} for k = 3,4,5 in O(n^{1-1/k}) rounds. This is a polynomial improvement upon the previous running times; for example, our C₆-detection algorithm runs in O(n^{2/3}) rounds, compared to O(n^{3/4}) in prior work. Finally, using our improved C₆-freeness algorithm, and the barrier on proving lower bounds on triangle-freeness of Eden et al., we show that improving the current ̃Ω(√n) lower bound for C₆-freeness of Korhonen et al. by any polynomial factor would imply strong circuit complexity lower bounds.
Cite as

Keren Censor-Hillel, Orr Fischer, Tzlil Gonen, François Le Gall, Dean Leitersdorf, and Rotem Oshman. Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs. In 34th International Symposium on Distributed Computing (DISC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 179, pp. 33:1-33:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2020.33,
  author =	{Censor-Hillel, Keren and Fischer, Orr and Gonen, Tzlil and Le Gall, Fran\c{c}ois and Leitersdorf, Dean and Oshman, Rotem},
  title =	{{Fast Distributed Algorithms for Girth, Cycles and Small Subgraphs}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{33:1--33:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Attiya, Hagit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.33},
  URN =		{urn:nbn:de:0030-drops-131115},
  doi =		{10.4230/LIPIcs.DISC.2020.33},
  annote =	{Keywords: distributed graph algorithms, cycles, girth, Congested Clique, CONGEST}
}
Document
Keynote Abstract
DOI: 10.4230/LIPIcs.OPODIS.2019.2
Distributed Optimization And Approximation: How Difficult Can It Be? (Keynote Abstract)

Authors: Keren Censor-Hillel

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
We know that exact distributed algorithms for optimization problems cannot be fast. To overcome these barriers, very efficient approximation algorithms have been designed in various distributed settings. But for very small approximation factors, a mystery remains: Why do we not have fast distributed algorithms for very small approximations factors in bandwidth restricted settings? This talk will overview the state-of-the-art of distributed optimization and approximation algorithms and discuss the major challenges in determining the complexity of small approximations.
Cite as

Keren Censor-Hillel. Distributed Optimization And Approximation: How Difficult Can It Be? (Keynote Abstract). In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, p. 2:1, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{censorhillel:LIPIcs.OPODIS.2019.2,
  author =	{Censor-Hillel, Keren},
  title =	{{Distributed Optimization And Approximation: How Difficult Can It Be?}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{2:1--2:1},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.2},
  URN =		{urn:nbn:de:0030-drops-117886},
  doi =		{10.4230/LIPIcs.OPODIS.2019.2},
  annote =	{Keywords: Distributed graph algorithms, Optimization and approximations}
}
Document
DOI: 10.4230/LIPIcs.DISC.2019.10
Erasure Correction for Noisy Radio Networks

Authors: Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic

Published in: LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019)

Abstract
The radio network model is a well-studied model of wireless, multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random. In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a non-adaptive protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of poly(log Delta, log log n) rounds where n is the number nodes in the network and Delta is the max degree. Moreover, we demonstrate that, even if the simulated protocol is not non-adaptive, it can be simulated with a multiplicative O(Delta log ^2 Delta) cost in the number of rounds. Lastly, we argue that simulations with a multiplicative overhead of o(log Delta) are unlikely to exist by proving that an Omega(log Delta) multiplicative round overhead is necessary under certain natural assumptions.
Cite as

Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, and Goran Zuzic. Erasure Correction for Noisy Radio Networks. In 33rd International Symposium on Distributed Computing (DISC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 146, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2019.10,
  author =	{Censor-Hillel, Keren and Haeupler, Bernhard and Hershkowitz, D. Ellis and Zuzic, Goran},
  title =	{{Erasure Correction for Noisy Radio Networks}},
  booktitle =	{33rd International Symposium on Distributed Computing (DISC 2019)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-126-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{146},
  editor =	{Suomela, Jukka},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.10},
  URN =		{urn:nbn:de:0030-drops-113170},
  doi =		{10.4230/LIPIcs.DISC.2019.10},
  annote =	{Keywords: radio networks, erasure correction, noisy radio networks, protocol simulation, distributed computing models}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.132
Distributed Detection of Cliques in Dynamic Networks

Authors: Matthias Bonne and Keren Censor-Hillel

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
This paper provides an in-depth study of the fundamental problems of finding small subgraphs in distributed dynamic networks. While some problems are trivially easy to handle, such as detecting a triangle that emerges after an edge insertion, we show that, perhaps somewhat surprisingly, other problems exhibit a wide range of complexities in terms of the trade-offs between their round and bandwidth complexities. In the case of triangles, which are only affected by the topology of the immediate neighborhood, some end results are: - The bandwidth complexity of 1-round dynamic triangle detection or listing is Theta(1). - The bandwidth complexity of 1-round dynamic triangle membership listing is Theta(1) for node/edge deletions, Theta(n^{1/2}) for edge insertions, and Theta(n) for node insertions. - The bandwidth complexity of 1-round dynamic triangle membership detection is Theta(1) for node/edge deletions, O(log n) for edge insertions, and Theta(n) for node insertions. Most of our upper and lower bounds are tight. Additionally, we provide almost always tight upper and lower bounds for larger cliques.
Cite as

Matthias Bonne and Keren Censor-Hillel. Distributed Detection of Cliques in Dynamic Networks. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 132:1-132:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{bonne_et_al:LIPIcs.ICALP.2019.132,
  author =	{Bonne, Matthias and Censor-Hillel, Keren},
  title =	{{Distributed Detection of Cliques in Dynamic Networks}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{132:1--132:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.132},
  URN =		{urn:nbn:de:0030-drops-107082},
  doi =		{10.4230/LIPIcs.ICALP.2019.132},
  annote =	{Keywords: distributed computing, subgraph detection, dynamic graphs}
}
Document
Track C: Foundations of Networks and Multi-Agent Systems: Models, Algorithms and Information Management
DOI: 10.4230/LIPIcs.ICALP.2019.135
Distributed Reconfiguration of Maximal Independent Sets

Authors: Keren Censor-Hillel and Mikaël Rabie

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
In this paper, we investigate a distributed maximal independent set (MIS) reconfiguration problem, in which there are two maximal independent sets for which every node is given its membership status, and the nodes need to communicate with their neighbors in order to find a reconfiguration schedule that switches from the first MIS to the second. Such a schedule is a list of independent sets that is restricted by forbidding two neighbors to change their membership status at the same step. In addition, these independent sets should provide some covering guarantee. We show that obtaining an actual MIS (and even a 3-dominating set) in each intermediate step is impossible. However, we provide efficient solutions when the intermediate sets are only required to be independent and 4-dominating, which is almost always possible, as we fully characterize. Consequently, our goal is to pin down the tradeoff between the possible length of the schedule and the number of communication rounds. We prove that a constant length schedule can be found in O(MIS+R32) rounds, where MIS is the complexity of finding an MIS in a worst-case graph and R32 is the complexity of finding a (3,2)-ruling set. For bounded degree graphs, this is O(log^*n) rounds and we show that it is necessary. On the other extreme, we show that with a constant number of rounds we can find a linear length schedule.
Cite as

Keren Censor-Hillel and Mikaël Rabie. Distributed Reconfiguration of Maximal Independent Sets. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 135:1-135:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2019.135,
  author =	{Censor-Hillel, Keren and Rabie, Mika\"{e}l},
  title =	{{Distributed Reconfiguration of Maximal Independent Sets}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{135:1--135:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.135},
  URN =		{urn:nbn:de:0030-drops-107111},
  doi =		{10.4230/LIPIcs.ICALP.2019.135},
  annote =	{Keywords: distributed graph algorithms, reconfiguration, maximal independent set}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.4
Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model

Authors: Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
We show how to multiply two n x n matrices S and T over semirings in the Congested Clique model, where n nodes communicate in a fully connected synchronous network using O(log{n})-bit messages, within O(nz(S)^{1/3} nz(T)^{1/3}/n + 1) rounds of communication, where nz(S) and nz(T) denote the number of non-zero elements in S and T, respectively. By leveraging the sparsity of the input matrices, our algorithm greatly reduces communication costs compared with general multiplication algorithms [Censor-Hillel et al., PODC 2015], and thus improves upon the state-of-the-art for matrices with o(n^2) non-zero elements. Moreover, our algorithm exhibits the additional strength of surpassing previous solutions also in the case where only one of the two matrices is such. Particularly, this allows to efficiently raise a sparse matrix to a power greater than 2. As applications, we show how to speed up the computation on non-dense graphs of 4-cycle counting and all-pairs-shortest-paths. Our algorithmic contribution is a new deterministic method of restructuring the input matrices in a sparsity-aware manner, which assigns each node with element-wise multiplication tasks that are not necessarily consecutive but guarantee a balanced element distribution, providing for communication-efficient multiplication. Moreover, this new deterministic method for restructuring matrices may be used to restructure the adjacency matrix of input graphs, enabling faster deterministic solutions for graph related problems. As an example, we present a new sparsity aware, deterministic algorithm which solves the triangle listing problem in O(m/n^{5/3} + 1) rounds, a complexity that was previously obtained by a randomized algorithm [Pandurangan et al., SPAA 2018], and that matches the known lower bound of Omega~(n^{1/3}) when m=n^2 of [Izumi and Le Gall, PODC 2017, Pandurangan et al., SPAA 2018]. Naturally, our triangle listing algorithm also implies triangle counting within the same complexity of O(m/n^{5/3} + 1) rounds, which is (possibly more than) a cubic improvement over the previously known deterministic O(m^2/n^3)-round algorithm [Dolev et al., DISC 2012].
Cite as

Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 4:1-4:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2018.4,
  author =	{Censor-Hillel, Keren and Leitersdorf, Dean and Turner, Elia},
  title =	{{Sparse Matrix Multiplication and Triangle Listing in the Congested Clique Model}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{4:1--4:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.4},
  URN =		{urn:nbn:de:0030-drops-100645},
  doi =		{10.4230/LIPIcs.OPODIS.2018.4},
  annote =	{Keywords: congested clique, matrix multiplication, triangle listing}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2018.7
The Sparsest Additive Spanner via Multiple Weighted BFS Trees

Authors: Keren Censor-Hillel, Ami Paz, and Noam Ravid

Published in: LIPIcs, Volume 125, 22nd International Conference on Principles of Distributed Systems (OPODIS 2018)

Abstract
Spanners are fundamental graph structures that sparsify graphs at the cost of small stretch. In particular, in recent years, many sequential algorithms constructing additive all-pairs spanners were designed, providing very sparse small-stretch subgraphs. Remarkably, it was then shown that the known (+6)-spanner constructions are essentially the sparsest possible, that is, larger additive stretch cannot guarantee a sparser spanner, which brought the stretch-sparsity trade-off to its limit. Distributed constructions of spanners are also abundant. However, for additive spanners, while there were algorithms constructing (+2) and (+4)-all-pairs spanners, the sparsest case of (+6)-spanners remained elusive. We remedy this by designing a new sequential algorithm for constructing a (+6)-spanner with the essentially-optimal sparsity of O~(n^{4/3}) edges. We then show a distributed implementation of our algorithm, answering an open problem in [Keren Censor{-}Hillel et al., 2016]. A main ingredient in our distributed algorithm is an efficient construction of multiple weighted BFS trees. A weighted BFS tree is a BFS tree in a weighted graph, that consists of the lightest among all shortest paths from the root to each node. We present a distributed algorithm in the CONGEST model, that constructs multiple weighted BFS trees in |S|+D-1 rounds, where S is the set of sources and D is the diameter of the network graph.
Cite as

Keren Censor-Hillel, Ami Paz, and Noam Ravid. The Sparsest Additive Spanner via Multiple Weighted BFS Trees. In 22nd International Conference on Principles of Distributed Systems (OPODIS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 125, pp. 7:1-7:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2018.7,
  author =	{Censor-Hillel, Keren and Paz, Ami and Ravid, Noam},
  title =	{{The Sparsest Additive Spanner via Multiple Weighted BFS Trees}},
  booktitle =	{22nd International Conference on Principles of Distributed Systems (OPODIS 2018)},
  pages =	{7:1--7:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-098-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{125},
  editor =	{Cao, Jiannong and Ellen, Faith and Rodrigues, Luis and Ferreira, Bernardo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2018.7},
  URN =		{urn:nbn:de:0030-drops-100676},
  doi =		{10.4230/LIPIcs.OPODIS.2018.7},
  annote =	{Keywords: Distributed graph algorithms, congest model, weighted BFS trees, additive spanners}
}
Document
DOI: 10.4230/LIPIcs.OPODIS.2017.21
Fast Distributed Approximation for TAP and 2-Edge-Connectivity

Authors: Keren Censor-Hillel and Michal Dory

Published in: LIPIcs, Volume 95, 21st International Conference on Principles of Distributed Systems (OPODIS 2017)

Abstract
The tree augmentation problem (TAP) is a fundamental network design problem, in which the input is a graph G and a spanning tree T for it, and the goal is to augment T with a minimum set of edges Aug from G, such that T ∪ Aug is 2-edge-connected. TAP has been widely studied in the sequential setting. The best known approximation ratio of 2 for the weighted case dates back to the work of Frederickson and JáJá, SICOMP 1981. Recently, a 3/2-approximation was given for the unweighted case by Kortsarz and Nutov, TALG 2016, and recent breakthroughs by Adjiashvili, SODA 2017, and by Fiorini et al., 2017, give approximations better than 2 for bounded weights. In this paper, we provide the first fast distributed approximations for TAP. We present a distributed 2-approximation for weighted TAP which completes in O(h) rounds, where h is the height of T . When h is large, we show a much faster 4-approximation algorithm for the unweighted case, completing in O(D + (√n) log^{*} n) rounds, where n is the number of vertices and D is the diameter of G. Immediate consequences of our results are an O(D)-round 2-approximation algorithm for the minimum size 2-edge-connected spanning subgraph, which significantly improves upon the running time of previous approximation algorithms, and an O(hMST + (√n)log^{*} n)-round 3- approximation algorithm for the weighted case, where hMST is the height of the MST of the graph. Additional applications are algorithms for verifying 2-edge-connectivity and for augment- ing the connectivity of any connected spanning subgraph to 2. Finally, we complement our study with proving lower bounds for distributed approximations of TAP.
Cite as

Keren Censor-Hillel and Michal Dory. Fast Distributed Approximation for TAP and 2-Edge-Connectivity. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 95, pp. 21:1-21:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.OPODIS.2017.21,
  author =	{Censor-Hillel, Keren and Dory, Michal},
  title =	{{Fast Distributed Approximation for TAP and 2-Edge-Connectivity}},
  booktitle =	{21st International Conference on Principles of Distributed Systems (OPODIS 2017)},
  pages =	{21:1--21:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-061-3},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{95},
  editor =	{Aspnes, James and Bessani, Alysson and Felber, Pascal and Leit\~{a}o, Jo\~{a}o},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2017.21},
  URN =		{urn:nbn:de:0030-drops-86475},
  doi =		{10.4230/LIPIcs.OPODIS.2017.21},
  annote =	{Keywords: approximation algorithms, distributed network design, connectivity augmentation}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2018.50
Making Asynchronous Distributed Computations Robust to Channel Noise

Authors: Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler

Published in: LIPIcs, Volume 94, 9th Innovations in Theoretical Computer Science Conference (ITCS 2018)

Abstract
We consider the problem of making distributed computations robust to noise, in particular to worst-case (adversarial) corruptions of messages. We give a general distributed interactive coding scheme which simulates any asynchronous distributed protocol while tolerating a maximal corruption level of \Theta(1/n)-fraction of all messages. Our noise tolerance is optimal and is obtained with only a moderate overhead in the number of messages. Our result is the first fully distributed interactive coding scheme in which the topology of the communication network is not known in advance. Prior work required either a coordinating node to be connected to all other nodes in the network or assumed a synchronous network in which all nodes already know the complete topology of the network. Overcoming this more realistic setting of an unknown topology leads to intriguing distributed problems, in which nodes try to learn sufficient information about the network topology in order to perform efficient coding and routing operations for coping with the noise. What makes these problems hard is that these topology exploration computations themselves must already be robust to noise.
Cite as

Keren Censor-Hillel, Ran Gelles, and Bernhard Haeupler. Making Asynchronous Distributed Computations Robust to Channel Noise. In 9th Innovations in Theoretical Computer Science Conference (ITCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 94, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.ITCS.2018.50,
  author =	{Censor-Hillel, Keren and Gelles, Ran and Haeupler, Bernhard},
  title =	{{Making Asynchronous Distributed Computations Robust to Channel Noise}},
  booktitle =	{9th Innovations in Theoretical Computer Science Conference (ITCS 2018)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-060-6},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{94},
  editor =	{Karlin, Anna R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2018.50},
  URN =		{urn:nbn:de:0030-drops-83184},
  doi =		{10.4230/LIPIcs.ITCS.2018.50},
  annote =	{Keywords: Distributed Computation, Coding for Interactive Communication, Noise- Resilient Computation, Coding Theory}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.10
Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model

Authors: Keren Censor-Hillel, Seri Khoury, and Ami Paz

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
We present the first super-linear lower bounds for natural graph problems in the CONGEST model, answering a long-standing open question. Specifically, we show that any exact computation of a minimum vertex cover or a maximum independent set requires a near-quadratic number of rounds in the CONGEST model, as well as any algorithm for computing the chromatic number of the graph. We further show that such strong lower bounds are not limited to NP-hard problems, by showing two simple graph problems in P which require a quadratic and near-quadratic number of rounds. Finally, we address the problem of computing an exact solution to weighted all-pairs-shortest-paths (APSP), which arguably may be considered as a candidate for having a super-linear lower bound. We show a simple linear lower bound for this problem, which implies a separation between the weighted and unweighted cases, since the latter is known to have a sub-linear complexity. We also formally prove that the standard Alice-Bob framework is incapable of providing a super-linear lower bound for exact weighted APSP, whose complexity remains an intriguing open question.
Cite as

Keren Censor-Hillel, Seri Khoury, and Ami Paz. Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.10,
  author =	{Censor-Hillel, Keren and Khoury, Seri and Paz, Ami},
  title =	{{Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.10},
  URN =		{urn:nbn:de:0030-drops-79969},
  doi =		{10.4230/LIPIcs.DISC.2017.10},
  annote =	{Keywords: CONGEST, Lower Bounds, Minimum Vertex Cover, Chromatic Number, Weighted APSP}
}
Document
DOI: 10.4230/LIPIcs.DISC.2017.11
Derandomizing Local Distributed Algorithms under Bandwidth Restrictions

Authors: Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman

Published in: LIPIcs, Volume 91, 31st International Symposium on Distributed Computing (DISC 2017)

Abstract
This paper addresses the cornerstone family of local problems in distributed computing, and investigates the curious gap between randomized and deterministic solutions under bandwidth restrictions. Our main contribution is in providing tools for derandomizing solutions to local problems, when the n nodes can only send O(log n)-bit messages in each round of communication. We combine bounded independence, which we show to be sufficient for some algorithms, with the method of conditional expectations and with additional machinery, to obtain the following results. First, we show that in the Congested Clique model, which allows all-to-all communication, there is a deterministic maximal independent set (MIS) algorithm that runs in O(log^2 Delta) rounds, where Delta is the maximum degree. When Delta=O(n^(1/3)), the bound improves to O(log Delta). Adapting the above to the CONGEST model gives an O(D log^2 n)-round deterministic MIS algorithm, where D is the diameter of the graph. Apart from a previous unproven claim of a O(D log^3 n)-round algorithm, the only known deterministic solutions for the CONGEST model are a coloring-based O(Delta + log^* n)-round algorithm, where Delta is the maximal degree in the graph, and a 2^O(sqrt(log n log log n))-round algorithm, which is super-polylogarithmic in n. In addition, we deterministically construct a (2k-1)-spanner with O(kn^(1+1/k) log n) edges in O(k log n) rounds in the Congested Clique model. For comparison, in the more stringent CONGEST model, where the communication graph is identical to the input graph, the best deterministic algorithm for constructing a (2k-1)-spanner with O(kn^(1+1/k)) edges runs in O(n^(1-1/k)) rounds.
Cite as

Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing Local Distributed Algorithms under Bandwidth Restrictions. In 31st International Symposium on Distributed Computing (DISC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 91, pp. 11:1-11:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{censorhillel_et_al:LIPIcs.DISC.2017.11,
  author =	{Censor-Hillel, Keren and Parter, Merav and Schwartzman, Gregory},
  title =	{{Derandomizing Local Distributed Algorithms under Bandwidth Restrictions}},
  booktitle =	{31st International Symposium on Distributed Computing (DISC 2017)},
  pages =	{11:1--11:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-053-8},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{91},
  editor =	{Richa, Andr\'{e}a},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2017.11},
  URN =		{urn:nbn:de:0030-drops-79759},
  doi =		{10.4230/LIPIcs.DISC.2017.11},
  annote =	{Keywords: Local problems, congested clique, derandomization}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact